The prior art is replete with known data structures, techniques, and systems related to data lookup tables and the processing of lookup queries. Data lookup techniques based upon data hashing are commonly used to handle large amounts of data, because hash-based techniques can usually be performed at a relatively high speed. A hash function can be applied to an input value to derive a corresponding output value. A hash table can be used to store data in locations (cells, slots, buckets, etc.) that are identified, labeled, or assigned based upon output values of a hashing function.
Cuckoo hashing is a known technique that can be utilized in a lookup table architecture. This technique was originally presented by Pagh and Rodler in Cuckoo Hashing, Proceedings of the 9th European Symposium on Algorithms (2001). Cuckoo hashing employs two hash functions and two respective hash tables (T1 and T2), which may be considered to be two portions or subtables of a single cuckoo hash table. Each entry is stored in a bucket of T1 or a bucket of T2, but never in both. FIG. 1 is a diagram of cuckoo hash tables arranged according to prior art principles. Here, the table T1 is identified by reference number 102 and the table T2 is identified by reference number 104. As explained by Pagh and Rodler, a given key will be hashed by the first hash function to determine its bucket in table T1 and that same key will be hashed by the second hash function to determine its bucket in table T2. In other words, using the same nomenclature as Pagh and Rodler, T1[h1(x)]=x and T2[h2(x)]=x, where h1 is the first hash function, h2 is the second hash function, and x is the key.
In practice, therefore, a given key is hashed using the two different hash functions to obtain two possible cuckoo hash table locations or buckets (alternatively, a single hash function with multiple results can be used). Then, those buckets can be searched for the key. If the key is found in one of the two buckets, then data stored with that key can be accessed, retrieved, processed, etc. As an example, FIG. 1 illustrates that Key A can be potentially stored in its respective bucket 106 in table 102 or in its respective bucket 108 in table 104. The arrow between bucket 106 and bucket 108 indicates potential movement or pushing of Key A between bucket 106 and bucket 108. As depicted in FIG. 1, Key B has its potential locations in table 102 and table 104, Key C has its potential locations in table 102 and table 104, and Key D has its potential locations in table 102 and table 104. In practice, table 102 and/or table 104 can include a number of empty buckets 110 to accommodate the insertion of new keys (and corresponding data) and to accommodate pushing of existing keys between table 102 and table 104.
A hash function may generate the same hash value (i.e., a locator or identifier for a given bucket) for two or more different input values. In other words, given a first key x1 and a second key x2, h1(x1) might equal h1(x2). In a cuckoo hash table, collisions are handled by moving entries from one table to another. With this in mind, FIG. 2 and FIG. 3 are diagrams (used for purposes of this simplified example) that illustrate pushing of keys in cuckoo hash tables. FIG. 2 depicts the status of the first table 202 and the second table 204 at a time when an entry (Entry X, which includes Key X and corresponding data) is to be inserted. The shaded areas represent occupied or unavailable buckets in the table. As explained above, the two hash functions indicate that Entry X can be inserted into the bucket 206 of table 202 or into the bucket 208 of table 204 (but not both). This example represents an attempt to initially insert Entry X into bucket 206. The arrows in FIG. 2 and FIG. 3 indicate the manner in which the given entry can be pushed from table 202 to table 204, or vice versa. Thus, referring to FIG. 2, although Entry Y is contained in bucket 206, it may alternatively be contained in the bucket 210 of table 204. Similarly, although Entry Z is presently contained in bucket 210, it may be pushed into the bucket 212 of table 202—note that bucket 210 may contain either Entry Y or Entry Z, meaning that the hash function h2(x) will generate the same value (corresponding to bucket 210) using either Entry Y or Entry Z as an input value. Moreover, Entry V can be moved from its current location (the bucket 214 of table 204) to its alternative location, namely, bucket 212 of table 202. FIG. 3 depicts the status of the first table 202 and the second table 204 after insertion of Entry X and pushing of Entry Y and Entry Z. As shown, Entry X is now contained in bucket 206. Entry X displaced Entry Y, which has been pushed to bucket 210. In turn, Entry Y displaced Entry Z, which has been pushed to bucket 212. The insertion of Entry X was possible because bucket 212 of table 202 was empty prior to the insertion operation (see FIG. 2). If the cuckoo hash tables are appropriately sized and managed, then enough empty buckets can be maintained to ensure that insertion and other operations do not fail.
Also in the literature are extensions of cuckoo hashing to more than two hash functions and multiple slots per bucket. In practice, the number of hash functions and/or the number of slots per bucket are increased because doing so greatly increases the theoretical and practical performance of the cuckoo hash table.
Conventional techniques related to lookups using a cuckoo hash table relate to manipulation using only one processor device or only one processor core. Thus, conventional techniques accommodate one insert operation, one delete operation, or one lookup operation at a time. Many modern applications, such as wireless switches and network routers, employ multiple processors and/or multiple processor cores. For example, some wireless switch components utilize a 32-core processing architecture for increased speed, capacity, and efficiency. The need exists for a system and related operating methodologies that can accommodate concurrent processing of a cuckoo hash table in a manner that avoids potentially invalid conditions that might arise when two or more processors attempt concurrent operations on the cuckoo hash table.